# 给定一个二叉树，我们在树的节点上安装摄像头。
#  节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
#  计算监控树的所有节点所需的最小摄像头数量。
#
#  示例 1：
#  输入：[0,0,null,0,0]
# 输出：1
# 解释：如图所示，一台摄像头足以监控所有节点。
#

#  示例 2：
#  输入：[0,0,null,0,null,0,null,null,0]
# 输出：2
# 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
from com.example.tree.tree_node import TreeNode


class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        res = 0

        def dfs(node: TreeNode) -> int:
            """
            :param node:
            :return: state  0 没覆盖; 1 覆盖, 没放相机; 2 覆盖, 有放相机
            """
            if not node:
                return 1
            leftState = dfs(node.left)
            rightState = dfs(node.right)
            nonlocal res
            if leftState == 0 or rightState == 0:
                res += 1
                return 2
            elif leftState == 2 or rightState == 2:
                return 1
            else:
                return 0

        return res + 1 if not dfs(root) else res


if __name__ == "__main__":
    #           0
    #      0
    #   0     0
    root = TreeNode(0)
    root.left = TreeNode(0)
    root.left.left, root.left.right = TreeNode(0), TreeNode(0)

    # [0, 0, null, 0, null, 0, null, null, 0]
    #              0
    #         0
    #     0
    #  0
    #    0
    # root = TreeNode(0)
    # root.left = TreeNode(0)
    # root.left.left = TreeNode(0)
    # root.left.left.left = TreeNode(0)
    # root.left.left.left.right = TreeNode(0)
    print(Solution().minCameraCover(root))

